from tools_algorithm import *

limit = 1000000
p = [True] * limit
for i in range(2, limit):
    for j in range(i * i, limit, i):
        p[j] = False


class Solution:
    def mostFrequentPrime(self, mat: List[List[int]]) -> int:

        m, n = len(mat), len(mat[0])
        cnt = Counter()

        dist = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)]

        def f(i, j, k, num):
            if i < 0 or i >= m or j < 0 or j >= n:
                return
            num = num * 10 + mat[i][j]
            if num > 10 and p[num]:
                cnt[num] += 1
            f(i + dist[k][0], j + dist[k][1], k, num)

        for i in range(m):
            for j in range(n):
                for k in range(8):
                    f(i, j, k, 0)
        if len(cnt) == 0:
            return -1
        mx = max(cnt.values())
        return max(k for k, v in cnt.items() if v == mx)


s = Solution()
print(s.mostFrequentPrime([[1, 1], [9, 9], [1, 1]]))
